#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

// 磁盘访问序列自增id
int work_id_inc = 1;
// 制作磁盘访问表格
vector<pair<int, int>> track_dist; // {io_req_no, track_dist}
// define program
struct Work {
  int id, ht, trackId; //磁盘id, 到达时间，访问磁道id，
  int st, ed;          // start time, end time
  int need;       // 读写花费时间 5~10， 每个磁道读写时间一致
  int acces_time; // 开始时间
  int seek_dist;  // 寻道距离
  int read_time, seek_time;     // 读写时间， 寻道时间
  bool in_wait, is_ok, working; // progress status
  friend ostream &operator<<(ostream &out, const Work &w) {
    out << w.id << " " << w.ht << " " << w.trackId << " " << w.need << endl;
    return out;
  }
  bool operator<(const Work &w) const { return ht < w.ht; }
  bool operator==(Work *w) const { return id < w->id; }
};
struct WorkResult {
  int id, w, ht; //进程id, 优先级, 到达时间
  int ed, tl, rw,
      cpt; // 结束时间，使用的时间片数量，就绪等待时间， CPU 占用时间
  int iow, iot, turn,
      turn_w; // IO等待时间， IO占用时间，周转时间， 带权周转时间
  vector<pair<int, int>>
      jobs; // 片段序列 first is type { cpu | io { 1 | 2, second is time { 200
  friend ostream &operator<<(ostream &out, const WorkResult &w) {
    out << " "
        << " " << w.id << " " << w.w << " " << w.ht << " " << w.ed << " "
        << w.tl << " " << w.rw << " " << w.cpt << " " << w.iow << " " << w.iot
        << endl;
    return out;
  }
};

// sstf 需要一个等待队列
vector<Work *> qwait;
void datacreate(int n) {
  if (n < 10 && n > 100) {
    cout << "磁盘访问数量需要在10 ～ 100 之间" << endl;
    exit(1);
  }
  fstream f("job", ios::out);
  vector<Work> jobs;
  f << n << endl;
  for (int i = 0; i < n; i++) {
    Work w = {.id = work_id_inc++,
              .ht = rand() % 200,
              .trackId = rand() % 200,
              .need = rand() % 6 + 5};
    jobs.push_back(w);
  }
  sort(jobs.begin(), jobs.end());
  for (auto x : jobs) {
    f << x;
  }
  f.close();
}

void init(int n) { datacreate(n); }
vector<Work *> jobs;
// 读取数据
void input() {
  fstream f("fixed_job", ios::in);
  int n;
  f >> n;
  while (n--) {
    Work *t = new Work{};
    f >> t->id >> t->ht >> t->trackId >> t->need;
    jobs.push_back(t);
  }
}
// 初始磁头位置
int dist_pointer = 143;
// req_no 磁道位置
int FCFS(const int req_no, Work *const w) {
  int dist = 0;
  dist = abs(dist_pointer - req_no);
  track_dist.push_back({req_no, dist});
  w->seek_dist = dist;
  dist_pointer = req_no;
  w->is_ok = true;
  return dist * 2;
}
// req_no 没有意义
int SSTF(const int _req_no, Work *const w, int time) {
  int min = 0x3f3f3f3f;
  Work *t = nullptr;
  for (auto x : qwait) {
    if (x->is_ok)
      continue;
    int dist = abs(dist_pointer - x->trackId);
    if (min > dist) {
      min = dist;
      t = x;
    }
  }
  if (t == nullptr) {
    cout << " 程序出现错误" << endl;
    exit(1);
  }

  // cout << " 正在处理" << t->id << endl;
  dist_pointer = t->trackId;
  t->st = time;
  t->seek_dist = min;
  t->is_ok = true;
  track_dist.push_back({t->trackId, min});
  return min * 2;
}
// req_no 没有意义
int EA(const int _req_no, Work *const w, const int tracK_len, int time) {
  int min = 0x3f3f3f3f, max = 0;
  Work *t = nullptr;
  for (auto x : qwait) {
    if (x->is_ok)
      continue;
    max = std::max(max, x->trackId);
  }
  bool walkUp = dist_pointer < max; // 能网上走我就，往上走
  for (auto x : qwait) {
    if (x->is_ok)
      continue;
    // cout << (walkUp && x->trackId < dist_pointer) << " ";
    if (walkUp && x->trackId < dist_pointer)
      continue;
    int dist = abs(dist_pointer - x->trackId);
    if (min > dist) {
      min = dist;
      t = x;
    }
  }
  cout << endl;
  if (t == nullptr) {
    cout << " 程序出现错误" << endl;
    exit(1);
  }
  cout << " 正在处理" << t->id << endl;
  dist_pointer = t->trackId;
  t->is_ok = true;
  t->st = time;
  t->seek_dist = min;
  track_dist.push_back({t->trackId, min});
  return min * 2;
}
// type
int handle_disk_req(const int _req_no, Work *const w, const int tracK_len,
                    int time, const int type) {
  switch (type) {
  case 1: {
    return FCFS(_req_no, w);
  }
  case 2: {
    return SSTF(0, nullptr, time);
  }
  case 3: {
    return EA(0, nullptr, tracK_len, time);
  }
  default: {
    return 1;
    break;
  }
  }
}

bool cpu = false;

int main(int argc, char *argv[]) {
  // init(10);
  input();
  Work *cpuworkingWork = nullptr;
  for (int i = 0; i < 1999; i++) {
    if (cpu && cpuworkingWork != nullptr) {
      // 磁头移动消耗的时间
      // cout << " 正在处理" << cpuworkingWork->id << endl; // FCFS 有效果
      for (auto x : qwait) {
        cout << x->id << " ";
      }
      cout << endl;
      int trackNeed =
          handle_disk_req(cpuworkingWork->trackId, cpuworkingWork, i, 200, 3);
      // 读写耗费时间
      i += trackNeed + cpuworkingWork->need;
      cpuworkingWork->ed = i;
      cpu = false;
      cpuworkingWork = nullptr;
    }

    for (auto x : jobs) {
      if (x->in_wait)
        continue;
      if (x->ht <= i) {
        x->in_wait = true;
        qwait.push_back(x);
      }
    }
    if (!cpu && cpuworkingWork == nullptr) {
      for (auto x : qwait) {
        if (x->is_ok)
          continue;
        if (cpu)
          continue;
        cpuworkingWork = x;
        cpu = true;
      }
    }
  }
  // 写入文件
  fstream f("disks", ios::out);
  cout << jobs.size() << endl;
  for (auto x : jobs) {
    f << x->id << " " << x->ht << " " << x->ed << " " << x->trackId << " "
      << x->seek_dist << " " << x->need << " " << x->st << " " << endl;
  }

  for (auto x : track_dist) {
    cout << x.first << "\t";
  }
  int sum = 0;
  cout << endl;
  for (auto x : track_dist) {
    sum += x.second;
    cout << x.second << "\t";
  }
  cout << endl;
  cout << sum << "\t " << double(sum) / track_dist.size() << "\t ";

  return 0;
}
